package com.chao.stucture.stack;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Stack;

/**
 * @author : Rookie
 * @description : 栈 用数组实现
 * @date : 2022/11/7
 */
public class ArrayStack<E> {
    /**
     * 元素
     */
    private Object[] objs;
    /**
     * 定义栈帧，永远指向顶部元素
     */
    private int top;
    /**
     * 栈的大小
     */
    private int size;

    private static final int DEFAULT_INITIAL_CAPACITY = 2 << 4;

    public ArrayStack() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    public ArrayStack(int initialCapacity) {
        this.objs = new Object[initialCapacity];
        this.top = -1;
        this.size = initialCapacity;
    }

    public boolean isEmpty() {
        return this.top == -1;
    }

    public boolean isFull() {
        return top == size - 1;
    }

    public int size() {
        return this.top ++;
    }

    /**
     * 扩容
     * @param newSize
     */
    private void resize(int newSize) {
        Object[] newArray = new Object[newSize];
        System.arraycopy(objs, 0, newArray, 0, top + 1);
        objs = newArray;
        size = newSize;
    }

    /**
     * 入栈一个元素
     * @param element
     */
    public void push(E element) {
        if (isFull()) {
            resize(size * 2);
        }
        objs[++top] = element;
    }

    /**
     * 出栈一个元素
     */
    public E pop() {
        if (isEmpty()) {
            throw new RuntimeException("stack is empty!");
        } else {
            E e = (E) objs[top --];
            // 缩容
            if (top + 1 == size / 4 && size / 2 != 0) {
                resize(size / 2);
            }
            return e;
        }
    }

    /**
     * 获取栈顶元素
     * @return
     */
    public E top() {
        if (isEmpty()) {
            throw new RuntimeException("stack is empty!");
        }
        return (E) objs[top];
    }

    public void print() {
        StringBuffer sb = new StringBuffer();
        int index = this.top;
        System.out.println("当前栈顶指针是：" + this.top);
        while (index > -1) {
            E e = (E) objs[index];
            if (e != null) {
                sb.append(e).append(",");
            }
            index --;
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        ArrayStack<String> stringArrayStack = new ArrayStack<>();
        stringArrayStack.push("A");
        stringArrayStack.push("B");
        stringArrayStack.push("C");
        stringArrayStack.print();
        System.out.println(stringArrayStack.top());
        System.out.println("栈是否为空：" + stringArrayStack.isEmpty());
        System.out.println("栈的元素个数：" + stringArrayStack.size());
        stringArrayStack.pop();
        System.out.println(stringArrayStack.top());
        stringArrayStack.print();
    }
}
